package com.chj.jz.dp.class02;

//https://www.lintcode.com/problem/decode-ways/description
public class Code03_DecodeWays {
	/**
	 * @param s:
	 *            a string, encoded message
	 * @return: an integer, the number of ways decoding
	 */
	public static int numDecodings(String s) {
		// write your code here
		char[] ss = s.toCharArray();
		int n = ss.length;
		if (n == 0) {
			return 0;
		}

		int[] f = new int[n + 1];
		f[0] = 1;
		int i, j;
		for (i = 1; i <= n; i++) {
			f[i] = 0;
			if (ss[i - 1] >= '1' && ss[i - 1] <= '9') {
				f[i] += f[i - 1];
			}

			if (i > 1) {
				j = 10 * (ss[i - 2] - '0') + (ss[i - 1] - '0');
				if (ss[i - 2] != '0' && j >= 10 && j <= 26) {
					f[i] += f[i - 2];
				}
			}
		}

		return f[n];
	}

	public static void main(String[] args) {
		{
			String M = "12";
			System.out.println(numDecodings(M));
		}
		{
			String M = "10";
			System.out.println(numDecodings(M));
		}
	}
}
